template <class T> class MinHeap{
      
public: 
    MinHeap():n(0),size(128){val=new T[size];}
    ~MinHeap(){delete[] val;}
    void push(T item);
    T pop(void);
//    void print(void);
    int parent(int i){ return (i-1)/2;}
    int items(void){return n;}
  
    
protected:
    T * val;
    int n;
    int size;
};

template <class T> void MinHeap<T>::push(T item){

        int i=n;
        if(n>=size){
          T * newlocation=new T[size*2];
          memcpy(newlocation,val,sizeof(T)*size);
          delete[] val;
          val=newlocation;
          size=size*2;
        }
        
        val[n++]=item;
        
        while((i>0) && (val[parent(i)]>item)){
                    val[i]=val[parent(i)];
                    i=parent(i);
                    val[i]=item;
                  
        }

  }

template <class T> T MinHeap<T>::pop(void){
    T item,tmp;
    item=val[0];
    //balancear el MinHeap
    val[0]=val[--n];
    int p=0,h=1;
    bool invalid=((h<n)&&(val[p]>val[h])||((h+1<n)&&(val[h+1]<val[p])));                                  
    while(invalid){
        if((h+1>n)||(val[h+1]>val[h])){
               tmp=val[p];
               val[p]=val[h];
               val[h]=tmp;
               p=h;                           
        } else {
                tmp=val[p];
                val[p]=val[h+1];
                val[h+1]=tmp;
                p=h+1;    
       }
     h=p*2+1;                  
     invalid=((h<n)&&(val[p]>val[h])||((h+1<n)&&(val[h+1]<val[p])));                                  
    }
return item;          
}

/*template <class T> void MinHeap<T>::print(void){
  cout <<endl;
  int n_elem=1;
  
  while(n_elem<n){
    cout << endl;
    for(int i=(n_elem/2);i<(n_elem/2)+n_elem;i++)
            if(i<n)
                    cout << val[i] << " ";
          n_elem*=2;
      }
     cout << endl;
    for (int i=0;i<n;i++)
        cout << val[i] << " ";

}
*/
template <class T> class Heap{
      
public: 
    Heap():n(0),size(128){val=new T[size];}
    ~Heap(){delete[] val;}
    void push(T item);
    T pop(void);
//    void print(void);
    int parent(int i){ return (i-1)/2;}
    int items(void){return n;}
  
    
protected:
    T * val;
    int n;
    int size;
};

template <class T> void Heap<T>::push(T item){

        int i=n;
        if(n>=size){
          T * newlocation=new T[size*2];
          memcpy(newlocation,val,sizeof(T)*size);
          delete[] val;
          val=newlocation;
          size=size*2;
        }
        
        val[n++]=item;
        
        while((i>0) && (val[parent(i)]<item)){
                    val[i]=val[parent(i)];
                    i=parent(i);
                    val[i]=item;
                  
        }

  }

template <class T> T Heap<T>::pop(void){
    T item,tmp;
    item=val[0];
    //balancear el heap
    val[0]=val[--n];
    int p=0,h=1;
    bool invalid=((h<n)&&(val[p]<val[h])||((h+1<n)&&(val[p]<val[h+1])));                                  
    while(invalid){
        if((h+1>n)||(val[h+1]<val[h])){
               tmp=val[p];
               val[p]=val[h];
               val[h]=tmp;
               p=h;                           
        } else {
                tmp=val[p];
                val[p]=val[h+1];
                val[h+1]=tmp;
                p=h+1;    
       }
     h=p*2+1;                  
     invalid=((h<n)&&(val[p]<val[h])||((h+1<n)&&(val[p]<val[h+1])));                                  
    }
return item;          
}

/*template <class T> void Heap<T>::print(void){
  cout <<endl;
  int n_elem=1;
  
  while(n_elem<n){
    cout << endl;
    for(int i=(n_elem/2);i<(n_elem/2)+n_elem;i++)
            if(i<n)
                    cout << val[i] << " ";
          n_elem*=2;
      }
     cout << endl;
    for (int i=0;i<n;i++)
        cout << val[i] << " ";

}
*/


